#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        QS(nums, 0, nums.size() - 1);
        string s;
        for (auto& e : nums)
            s += to_string(e);
        if (s[0] == '0') return "0";
        return s;
    }

    bool cmpBig(int x, int y) {
        string xs = to_string(x) + to_string(y);
        string ys = to_string(y) + to_string(x);
        // long long xl = stoi(xs), yl = stoi(ys);
        int len = ys.size(), i = 0;
        while (i < len) {
            if (xs[i] > ys[i]) return true;
            else if (xs[i] == ys[i]) i++;
            else return false;
        }
        return false;
    }

    bool cmpEq(int x, int y) {
        string xs = to_string(x) + to_string(y);
        string ys = to_string(y) + to_string(x);
        int len = ys.size(), i = 0;
        while (i < len) {
            if (xs[i] > ys[i]) return false;
            else if (xs[i] == ys[i]) i++;
            else return false;
        }
        
        return true;
    }

    void QS(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int key = getkey(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (cmpBig(nums[i], key)) swap(nums[++left], nums[i++]);
            else if (cmpEq(nums[i], key)) i++;
            else swap(nums[--right], nums[i]);
        }

        QS(nums, l, left);
        QS(nums, right, r);
    }

    int getkey(vector<int>& nums, int l, int r) {
        int rx = l + rand() % (r - l + 1);
        return nums[rx];
    }
};

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        // if (nums.size() == 1)
        //     return 1;
        // // if (nums.size() == 2) {
        // //     if (nums[0] == nums[1]) return 1;
        // //     return 2;
        // // }
        // bool flag = false;
        // for (int i = 0; i < nums.size() - 1; i++) {
        //     if (nums[i] != nums[i + 1]) {
        //         flag = true;
        //         break;
        //     }
        // }
        // if (!flag) return 1;
        
        // int ret = 2;
        // for (int i = 1; i < nums.size() - 1; i++) {
        //     if (nums[i] == nums[i + 1]) {
        //         int left = nums[i - 1];
        //         int index = i - 1;
        //         while (nums[i] == nums[i + 1] && i < nums.size() - 1)
        //             i++;
        //         if (nums[i] >= left && nums[i] >= nums[i + 1] && index != 0 && i != nums.size() - 1)
        //             ret++;
        //         if (nums[i] <= left && nums[i] <= nums[i + 1] && index != 0 && i != nums.size() - 1)
        //             ret++;
        //     } else {
        //         if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
        //             ret++;
        //         if (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])
        //             ret++;
        //     }
        // }
        // return ret;
        int n = nums.size();
        if (n < 2) return n;
        int ret = 0, left = 0;
        for (int i = 0; i < n - 1; i++) {
            int right = nums[i + 1] - nums[i];
            if (right == 0) continue;
            if (right  * left <= 0) ret++;
            left = right;
        }
        return ret + 1;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0, len = prices.size();
        // int left = 0, right = 0;
        // while (right < len) {
        //     while (right < len - 1 && prices[right] < prices[right + 1])
        //         right++;
        //     int ret = max(0, prices[right] - prices[left]);
        //     sum += ret;
        //     left = right + 1;
        //     right = left;
        // }
        // return sum;

        for (int i = 0; i < len - 1; i++)
            if (prices[i + 1] > prices[i])
                sum += prices[i + 1] - prices[i];
        return sum;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0;
        int prevMin = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            ret = max(ret, prices[i] - prevMin);
            prevMin = min(prevMin, prices[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> ret;
        for (auto e : nums) {
            if (ret.empty() || e > ret.back()) {
                ret.push_back(e);
            } else {
                int left = 0, right = ret.size() - 1;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if  (ret[mid] < e) left = mid + 1;
                    else right = mid - 1;
                }
                ret[left] = e;
            }
        }


        return ret.size();
    }
};

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        vector<int> ret;
        for (auto e : nums) {
            
            if (ret.empty() || e > ret.back()) {
                ret.push_back(e);
            } else {
                int left = 0, right = ret.size() - 1;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (ret[mid] < e) left = mid + 1;
                    else right = mid;
                }
                ret[left] = e;
            }
            if (ret.size() >= 3) return true;
        }

        return false;
    }
};

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ret = 1;
        int len = nums.size(), right = 1, left = 0;
        while (right < len) {
            while (right < len && nums[right] > nums[right - 1])
                right++;
            ret = max(ret, right - left);
            left = right;
            right = left + 1;
        }

        return ret;
    }
};

int main() {


    return 0;
}